CF1198F GCD Groups 2

一道div1的F,神他喵居然是道玄学random_shuffle题？？？

然鹅也是需要一些贪心思路的呢，朴素随机wa的概率还是高的呢

题解：

考虑对打乱后序列正确性的判定及划分

我们注意到如果数$x$是某一组的gcd的倍数，那依照贪心的思路，它肯定不应该被放进那一组，而是放进另一组

于是我们可以做到$O(n)$判定

为什么这么random是对的呢？口胡一下就是一组数gcd=1的概率会随数的增加而呈指数级减小，完整证明可以看官方的

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int n,a[N],ans[N],b[N];

inline int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}

signed main(){
    read(n);
    srand(time(NULL));
    for(int i=1;i<=n;i++) read(a[i]),b[i]=i;
    long long begin_time=clock();
    while(clock()-begin_time<CLOCKS_PER_SEC*0.45){
        random_shuffle(b+1,b+1+n);
        int g1=0,g2=0;
        for(int i=1;i<=n;i++){
            int now=gcd(g1,a[b[i]]);
            if(now^g1){
                g1=now;
                ans[b[i]]=1;
            }
            else{
                g2=gcd(g2,a[b[i]]);
                ans[b[i]]=2;
            }
        }
        if(g1==1&&g2==1){
            puts("YES");
            for(int i=1;i<=n;i++) write(ans[i]),putchar(' ');
            return 0;
        }
    }
    puts("NO");
}